package com.adee.java;

import java.util.PriorityQueue;

/**
 * 优先队列PriorityQueue
 * https://blog.csdn.net/yzhcjl_/article/details/129212256
 *
 * 总结源码注释的意思 Java1.5中引入的
 * 1.基于优先级堆进行排序
 * 2.优先级队列不允许{@code null}元素 依赖于自然排序的优先级队列也不允许插入不可比较的对象 就可能导致ClassCastException异常
 * 3.优先级队列是无界的，但具有内部 容量控制用于存储队列中的元素。它总是至少和队列一样大
 * 4.此实现不同步如果想使用线程安全的，则使用PriorityBlockingQueue类
 *
 * 优先队列为什么采用堆结构？
 * 优先队列，基于小顶堆实现，只要保证时刻能持有元素集合中的最小（或最大）元素即可，不用全部排序，
 * 因此采用堆这种数据结构，堆插入或删除一个元素的时间复杂度为logN，而采用普通数组或顺序数组时，都会出现时间复杂度为N的情况。
 *
 * 	        入队	    出队
 * 普通数组	O(1)	O(n)
 * 顺序数组	O(n)	O(1)
 * 堆	    O(logn)	O(log)
 *
 */
public class Test056_PriorityQueue {
    public static void main(String[] args) {
        Student s1 = new Student(18, "Jack");
        Student s2 = new Student(16, "Rose");
        Student s3 = new Student(28, "Lily");
        Student s4 = new Student(22, "Tom");
        Student s5 = new Student(35, "Mike");

        // 优先队列，基于小顶堆实现
        PriorityQueue<Student> pq = new PriorityQueue<>();
        pq.add(s1);
        pq.add(s2);
        pq.add(s3);
        pq.add(s4);
        pq.add(s5);
        // pq.add(null); // 元素不可为null
        for (Student s : pq) {
            System.out.println(s);
        }
    }

    static class Student implements Comparable<Student> {
        int age;
        String name;
        public Student(int age, String name) {
            this.age = age;
            this.name = name;
        }


        @Override
        public int compareTo(Student other) {
            return this.age - other.age;
        }

        @Override
        public String toString() {
            return "Student{" +
                    "age=" + age +
                    ", name='" + name + '\'' +
                    '}';
        }
    }
}
